import time
import numpy as np

# 定义全局的一个中间变量，减少每次都要在内存中新创建的时间
tmp = []


def mergeList(arry: list[int], start: int, end: int):
    """
    将start到end之间的进行有序的合并
    :param arry:
    :param start:
    :param end:
    :return:
    """
    global tmp
    mid = (start + end) // 2
    left = start
    right = mid + 1
    # 每次比较两组的第一个数，将小的加入临时列表中
    while left < mid + 1 and right < end + 1:
        if arry[left] > arry[right]:
            tmp.append(arry[right])
            right += 1
        else:
            tmp.append(arry[left])
            left += 1
    # 当其中有一个已经全部加入，只需将两一个剩下的依次加入
    while left < mid + 1:
        tmp.append(arry[left])
        left += 1
    while right < end + 1:
        tmp.append(arry[right])
        right += 1

    # 将已经合并好的有序列表替换到原来的位置上去
    mergeListindex = 0
    for changeindex in range(start, end + 1):
        arry[changeindex] = tmp[mergeListindex]
        mergeListindex += 1
    tmp.clear()


def mergesort(arry: list[int], start: int, end: int):
    if end - start < 1:
        return
    else:
        mid = (start + end) // 2
        mergesort(arry, start, mid)
        mergesort(arry, mid + 1, end)
        mergeList(arry, start, end)


def main():
    count = input("请输入产生数组元素个数")
    a = np.random.randint(0, 2 ** 31 - 1, int(count)).tolist()
    print(a[1:10])
    time1 = time.perf_counter()
    start, end = 0, len(a) - 1
    mergesort(a, start, end)
    time2 = time.perf_counter()
    print(a[1:10])
    a.sort()
    print(a[1:10])
    print("程序运行时间：%f s" % (time2 - time1))


if __name__ == '__main__':
    main()
